package com.demo.java.OD601_650.OD616;

import java.util.Scanner;
import java.util.HashMap;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【单向链表中间节点(A卷-100分)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146867509
 */
public class OdMain {
    // 节点定义
    public static class ListNode {
        public int value;  // 节点的值
        public int next;   // 下一个节点的地址

        public ListNode(int value, int next) {
            this.value = value;
            this.next = next;
        }
    }

    public static void main(String[] args) {
        // 处理输入
        Scanner in = new Scanner(System.in);

        // 读取头节点的地址和节点数量
        String head_node_str = in.nextLine();
        String[] head_info = head_node_str.split(" ");
        int head_addr = Integer.valueOf(head_info[0]);
        int count = Integer.valueOf(head_info[1]);

        // 创建哈希表，存储节点地址到节点对象的映射
        HashMap<Integer, ListNode> node_info = new HashMap<>();

        // 遍历输入，构建链表
        for (int i = 0; i < count; i++) {
            String node_str = in.nextLine();
            String[] node_list_info = node_str.split(" ");
            int addr = Integer.valueOf(node_list_info[0]);  // 当前节点的地址
            int val = Integer.valueOf(node_list_info[1]);   // 当前节点的值
            int next = Integer.valueOf(node_list_info[2]);  // 当前节点指向的下一个节点地址
            ListNode temp_node = new ListNode(val, next);  // 创建节点对象
            node_info.put(addr, temp_node);  // 将节点地址和节点对象放入哈希表
        }

        // 构造链表，剔除无效节点
        int size = 1, cur = 0;
        ListNode head = node_info.get(head_addr);  // 获取头节点
        ListNode thead = head;

        // 计算链表的长度
        while (thead.next != -1) {
            size++;
            thead = node_info.get(thead.next);
        }

        // 找中间节点并输出其值
        while (head.next != -1) {
            if ((size / 2) == cur) {
                System.out.println(head.value);  // 输出中间节点的值
            }
            head = node_info.get(head.next);  // 移动到下一个节点
            cur++;
        }
    }
}